package Ep06_BinaryTree.DFS.T17_0113;

import Ep06_BinaryTree.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Jimmy Zhan WORKSTATION
 * @date 2023/5/29 11:10
 * 说明： lc 0113、
 * 笔记：
 * 递归中遍历全树为什么不需要返回值
 * 因为如果是只找其中一个解，就需要提前返回，找到即走
 * 如果是要找出所有解，那就需要遍历全树，不需要提前返回，记录每一条路径的path，和存放结果集的res，找完才能走，因此返回值没有意义
 */

public class Mine {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;

        List<Integer> path = new ArrayList<>();
        preorderdfs(root, targetSum, res, path);
        return res;
    }

    private void preorderdfs(TreeNode root, int targetSum, List<List<Integer>> res, List<Integer> path) {
        path.add(root.val);

        // 叶子结点，判断，如果符合要求就加入到结果集中
        if (root.left == null && root.right == null) {
            if (targetSum == root.val) {
                res.add(new ArrayList<>(path));
            }
            return;
        }

        // 非叶子节点，不遍历空节点
        if (root.left != null) {
            preorderdfs(root.left, targetSum - root.val, res, path);
            path.remove(path.size() - 1);   // 回溯
        }
        if (root.right != null) {
            preorderdfs(root.right, targetSum - root.val, res, path);
            path.remove(path.size() - 1);   // 回溯
        }
    }
}
